Модуларна аритметика
Два цела броја \(a\) и \(b\) су конгруентна по модулу \(n\) ако дају исти остатак при дељењу са \(n\), односно ако је њихова разлика \(a-b\) дељива са \(n\).
Извршавање аритметичких операција по модулу \(n\) подразумева да се након примене операције одреди остатак при дељењу са бројем \(n\). Важе следеће релације: \[\begin{eqnarray*} (a + b)\,\mathrm{mod}\,n &=& (a\,\mathrm{mod}\,n\ +\ b\,\mathrm{mod}\,n)\,\mathrm{mod}\,n\\ (a \cdot b)\,\mathrm{mod}\,n &=& (a\,\mathrm{mod}\,n\ \cdot\ b\,\mathrm{mod}\,n)\,\mathrm{mod}\,n\\ (b - a)\,\mathrm{mod}\,n &=& (b\,\mathrm{mod}\,n - a\,\mathrm{mod}\,n + n)\,\mathrm{mod}\,n \end{eqnarray*}\]
У пракси, ово је корисно у ситуацијама када збир \(a+b\) (односно производ \(a\cdot b\)) може премашити максималну подржану вредност одговарајућег типа података.
Докажимо релацију о производу (она о збиру се доказује још једноставније). Подсетимо се да је \(x\,\mathrm{mod}\,y = r\) ако и само ако постоји \(q\) такав да је \(x = q\cdot y + r\) и ако је \(0 \leq r < y\). Претпоставимо da je \(a = q_a\cdot n + r_a\) и \(b = q_b\cdot n + r_b\) за \(0 \leq r_a, r_b < n\). Тада важи да је \(a\cdot b = (q_a \cdot n + r_a) \cdot (q_b \cdot n + r_b) = (q_a \cdot q_b \cdot n + q_a \cdot r_b + r_a\cdot q_b)n + r_a\cdot r_b\). Ако важи да је \(r_a \cdot r_b = q\cdot n + r\) за \(0 \leq r < n\), тада је \(a\cdot b = (q_a \cdot q_b \cdot n + q_a \cdot r_b + r_a\cdot q_b + q)n + r\), па је \((a \cdot b)\,\mathrm{mod}\,n = r\). Важи да је \((a\,\mathrm{mod}\,n\ \cdot\ b\ mod\ n)\,\mathrm{mod}\,n = (r_a \cdot r_b)\,\mathrm{mod}\,n = r,\) чиме је тврђење доказано.
Докажимо релацију о разлици. Додавање броја \(n\) служи да се избегне дељење негативних бројева. Подсетимо се да је \(x\,\mathrm{mod}\,y = r\) ако и само ако постоји \(q\) такав да је \(x = q\cdot y + r\) и ако је \(0 \leq r < y\). Нека је \(a = q_a\cdot n + r_a\) и \(b = q_b\cdot n + r_b\), za \(0 \leq r_a, r_b < n\). Зато је \(a\,\mathrm{mod}\,n = r_a\) и \(b\,\mathrm{mod}\,n = r_b\). Нека је \(r_b - r_a + n = q\cdot n + r\) за неко \(0 \leq r < n\). Зато је \((a\,\mathrm{mod}\,n - b\,\mathrm{mod}\,n + n)\,\mathrm{mod}\,n = (r_b - r_a + n)\,\mathrm{mod}\,\ n = r.\) Такође, важи и да је \(b-a = (q_b - q_a)\cdot n + (r_b - r_a) = (q_b - q_a - 1)\cdot n + (r_b - r_a + n) = (q_b - q_a - 1 + q)\cdot n + r\), па је и \((b-a)\,\mathrm{mod}\,n = r\), чиме је тврђење доказано.
У наставку ћемо приказати неколико задатака у којима се примењује модуларна аритметика.